class Solution {
    int m,n,k;
    bool vis[101][101];
    int ret;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    int wardrobeFinishing(int _m, int _n, int cnt) {
        m=_m,n=_n,k=cnt;
        dfs(0,0);
        return ret;
    }
    void dfs(int i,int j)
    {
        ret++;
        vis[i][j]=true;
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k],y=j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n
            && !vis[x][y] && check(x,y))
            {
                dfs(x,y);
            }
        }
    }
    bool check(int i,int j)
    {
        int tmp=0;
        while(i)
        {
            tmp+=i%10;
            i/=10;
        }
        while(j)
        {
            tmp+=j%10;
            j/=10;
        }
        return tmp<=k;
    }
};
